In a computer controlled system, it is often important for the system to recognize one or more three dimensional objects (e.g., three dimensional polygons) from a two dimensional graphical representation of a scene. For example, in a computer controlled robotic system, a camera may capture and generate, in digital form, a two dimensional graphical representation of a scene including one or more three dimensional objects. The system must be able to recognize the three dimensional objects from the two dimensional graphical representation of the scene, so that the computer can control a robot to properly operate on, or in connection with, the three dimensional objects. Recognition of a three dimensional object becomes particularly complicated when only a part of the object is within the field of the camera, or when the object is partially occluded by other objects in the field of the camera. In such cases, the computer must recognize the object from partial contours found in the two dimensional, graphical representation of the scene which is in the field of the camera.
In the past, different techniques have been proposed to enable computer systems to recognize a three dimensional object from a two dimensional graphical representation of a scene. One technique, proposed by Bunke and Glauser, is designed to recognize polygons, and is based upon local shape descriptors (referred to as edge length ratios), which are invariant under affine transformations, i.e., translation, scaling, rotation and ortho-graphic projection from three dimensions to a two dimensional plane. The technique involves computation of dissimilarity measures between the edge length ratios for all of the edges of an unknown polygon contour, comparison of the dissimilarity measures with the edge length ratios associated with the edges of a set of known prototypes (which are known polygon contours), and identifying different portions of the unknown contour as one of the prototypes when the dissimilarity measure between the edge length ratios for three consecutive edges is below a threshold value.
In the foregoing technique, as proposed by Bunke and Glauser, the dissimilarity measure between two edge length ratios .lambda..sup.p.sub.i,j, .lambda..sup.u.sub.i,k for a prototype and unknown object, respectively, used the following formula: EQU d.sub.i (.lambda..sup.u.sub.i,k, .lambda..sup.p.sub.i,j)=.vertline..lambda..sup.u.sub.i,k /.lambda..sup.p.sub.i,j -1.vertline.; j=1, . . . , n.sub.p ; k=1, . . . , n.sub.u ; i=1, . . . ,4
Applicants believe the computation of dissimilarity measures by means of the Bunke and Glauser technique, does not lend itself readily to implementation in VLSI architectures. Specifically, applicants believe the circuitry required to handle the multiplication and division required for the Bunke and Glauser technique would be relatively slow and requires a large number of transistors (which would require a significant space) to implement the circuitry in VLSI architectures.